This invention relates to systems and methods for processing images using filters. More specifically, this invention relates to systems and methods for designing and implementing image processing filters using templates wherein the filters operate on gray-scale images and the templates identify gray-scale image features for the purposes of modification or for extracting some image statistic, and for the purposes of optimization for the human visual system, or compatibility with other system modules, such as, compression algorithms, recognition algorithms and those occurring in printing and display devices.
The following patents and publications are hereby incorporated by reference for their teachings:
xe2x80x9cMethod for design and implementations of an image resolution enhancement system that employs statistically generated lookup tables,xe2x80x9d Loce et al., U.S. Pat. No. 5,696,845;
xe2x80x9cMethod and apparatus for the resolution enhancement of grayscale images that include text and line artxe2x80x9d, Lin et al., U.S. Pat. No. 5,742,703.
Barski, L., and R. Gaborski, xe2x80x9cImage Character Enhancement using a Stroke Strengthening Kernel,xe2x80x9d U.S. Pat. No. 4,791,679, Dec. 13, 1988.
Bassetti, L. W., xe2x80x9cFine Line Enhancement,xe2x80x9d U.S. Pat. No. 4,544,264, Oct. 1, 1985.
Bunce, R., xe2x80x9cPixel Image Enhancement Employing a Reduced Template Memory Store,xe2x80x9d U.S. Pat. No. 5,237,646, Aug. 17, 1993.
Carely, A. L., xe2x80x9cResolution Enhancement in Laser Printers,xe2x80x9d Copyright 1993, XLI Corp., Woburn, Mass.
Crow, F. C., xe2x80x9cThe Use of Gray-scale for Improved Raster Display of Vectors and Characters,xe2x80x9d Computer Graphics, Vol. 12, August, 1978.
Curry, D. N., xe2x80x9cHyperacuity Laser Imager,xe2x80x9d Journal of Electronic Imaging, Vol. 2, No. 2, pp 138-146, April 1993.
Curry, D. N., R. St. John, and S. Filshtinsky, xe2x80x9cEnhanced Fidelity Reproduction of Images by Hierarchical Template Matching,xe2x80x9d U.S. Pat. No. 5,329,599, Jul. 12, 1994.
Denber, M., xe2x80x9cImage Quality Improvement by Hierarchical Pattern Matching with Variable Size Templates,xe2x80x9d U.S. Pat. No. 5,365,251, Nov. 15, 1994.
Frazier, A. L., and J. S. Pierson, xe2x80x9cResolution Transforming Raster-Based Imaging System,xe2x80x9d U.S. Pat. No. 5,134,495, Jul. 28, 1992.
Frazier, A. L., and J. S. Pierson, xe2x80x9cInterleaving Vertical Pixels in Raster-Based Laser Printers,xe2x80x9d U.S. Pat. No. 5,193,008, Mar. 9, 1993.
Handley, J., and E. R. Dougherty, xe2x80x9cModel-Based Optimal Restoration of Fax Images in the Context of Mathematical Morphology, Journal of Electronic Imaging, Vol. 3, No. 2, April 1994.
Kang, H., and R. Coward, xe2x80x9cArea Mapping Approach for Resolution Conversion,xe2x80x9d Xerox Disclosure Journal, Vol. 19, No. 2, March/April, 1994.
Loce, R. and E. Dougherty, Enhancement and Restoration of Digital Documents, SPIE Press, Bellingham Wash., 1997. Chapters 1-4.
Loce, R. P., M. S. Cianciosi, and R. V. Klassen, xe2x80x9cNon-integer Image Resolution Conversion Using Statistically Generated Look-Up Tables,xe2x80x9d U.S. Pat. No. 5,387,985, Feb. 7, 1995.
Mailloux, L. D., and R. E. Coward, xe2x80x9cBit-Map Image Resolution Converter,xe2x80x9d U.S. Pat. No. 5,282,057, Jan. 25, 1994.
Miller, S., xe2x80x9cMethod and Apparatus for Mapping Printer Resolution Using Look-up Tables,xe2x80x9d U.S. Pat. No. 5,265,176, Nov. 23, 1993.
Petrick, B., and P. Wingfield, xe2x80x9cMethod and Apparatus for Input Picture Enhancement by Removal of Undesired Dots and Voids.xe2x80x9d U.S. Pat. No. 4,646,355, Feb. 24, 1987.
Sanders, J. R., W. Hanson, M. Burke, R. S. Foresman, J. P. Fleming, xe2x80x9cBehind Hewlett-Packard""s Patent on Resolution Enhancement(copyright) Technology,xe2x80x9d B. Colgan, ed., Prepared by Torrey Pines Research Carlsbad Calif., Distributed by BIS CAP International, Newtonville Mass., 1990. [Dicusses early template matching patentsxe2x80x94Tung, Walsh, Basseti, . . . ]
Tung, C., xe2x80x9cPiece-Wise Print Image Enhancement for Dot Matrix Printers,xe2x80x9d U.S. Pat. No. 4,847,641, Jul. 11, 1989, U.S. Pat. No. 5,005,139, Apr. 2, 1991.
Tung, C., xe2x80x9cResolution Enhancement in Laser Printers,xe2x80x9d in Proc. SPIE 1912, Color Hard Copy and Graphics Arts II, Jan. 31, 1993, San Jose, Calif.
Walsh, B., F., and D. E. Halpert, xe2x80x9cLow Resolution Raster Images,xe2x80x9d U.S. Pat. No. 4,437,122, Mar. 13, 1984.
A wide variety of digital document processing tasks are performed using template-based filters. Illustratively, digital document processing tasks include resolution conversion, enhancement, restoration, appearance tuning and de-screening of images. These tasks are commonly performed on monochrome and color images, as well as binary and continuous tone images. Although, due to the binary nature of conventional templates, implementing many digital document-processing tasks on continuous tone images has been problematic prior to the present invention. A continuous tone image may also be referred to as a gray-scale image.
In conventional systems and methods, a typical filter includes template operators to perform filtering of the images, where, a filter may be characterized as an operator or device that transforms one image into another image or transforms an image to a collection of information, such as image statistics. The filter is formed of a number of imaging template operators, often simply referred to as templates. These templates may be, for example, stored in a look-up table and implemented using a look-up table formalism. Or other equivalent formalisms, such as Boolean logic may be employed. The number of templates in a filter may vary between a small number of templates to thousands of templates. Due to its versatility in design, a look-up table is typically used to implement a template-based filter.
A raster is a one-dimensional array of image data, reflecting a single line of data across a single dimension, i.e., the length or the width, of the image. Further, each location, or xe2x80x9cpicture element,xe2x80x9d in an image may be called a xe2x80x9cpixel.xe2x80x9d In an array defining an image in which each item of data provides a value, each value indicating the properties of a location may be called a pixel value. Each pixel value is a bit in a binary form of an image, a gray-scale value in a gray-scale form of an image, or a set of color-spaced coordinates in a color coordinate form of an image. The binary form, gray-scale form, and color coordinate form are each arranged typically in a two-dimensional array, which defines an image. An N-dimensional array is typically used for an N-dimensional images, where for example, N=3 for 3-dimensional topographic images.
Using the typical binary image processing setting as an example, the filter, using the templates, transforms certain observed pixel patterns in a binary image, for example, into a corresponding enhanced binary pixel pattern. Specifically, the filter observes an arrangement of pixels using a suitable window or mask. A window is an imaging algorithmic device that observes a plurality of pixels at the same time, where the plurality of pixels is located about a target pixel. The values and locations of the observed pixels are inputted into the template matching operations. After observing the arrangement of pixels, about a target pixel, the filter then attempts to match the observed pixel pattern with one or more of the templates in the look-up table. If the look-up table contains a match to the observed pixel pattern, the look-up table generates an appropriate output. The output may be an enhanced pixel pattern for the target pixel that corresponds to the observed pixel pattern. The output could also be information in other forms; for example, the output could be a code denoting the match condition, or a data to be used for a statistical characterization of image regions.
A wide variety of types and sizes of observation windows or masks are known. The particular window used in a particular application depends on the image to be analyzed and the particular process to be performed on the image. Illustratively, a 3xc3x973 window may be used to process an image. The 3xc3x973 window, at various locations in the image, observes a 3xc3x973 block, i.e., a 9-pixel block, of binary-valued pixels, for example. One pixel in the window is the target pixel, which is typically the center pixel, while the other pixels in the window are the neighboring pixels. The target pixel and the neighboring pixels form a neighborhood. The window is typically scanned across an image advancing from target pixel to target pixel.
After the neighborhood is observed in the window, the neighborhood is then processed in some manner. For example, the observed neighborhood may be transformed into a vector. The vector is expressed in the form of (x1, x2. . . xN) where Ni is the number of pixels in the neighborhood and is used to represent the properties of the target pixel, including the neighborhood of the target pixel. Each element of the vector represents one of the pixels observed in the window. The vector is then used in the look-up table to generate a desired output, for example.
A look-up table may be created in a wide variety of ways. Typically, an input value is input into the look-up table and, in response, the look-up table outputs an output value. Further, the look-up table is typically created using a training image or a set of training images. xe2x80x9cRestoration and Enhancement of Digital Documents,xe2x80x9d by R. Loce and E. Dougherty, teaches a variety of methods for designing templates based on sets of training images. The training images will occur in pairs, where one member is the xe2x80x9ctypically input image,xe2x80x9d or the xe2x80x9ctypically observed image,xe2x80x9d i.e., the xe2x80x9cobserved image,xe2x80x9d and the other image is the xe2x80x9cideal desired processed version of the image,xe2x80x9d i.e., the xe2x80x9cideal image.xe2x80x9d The training image pairs may be input into a computer program that acquires and analyzes pattern statistics between the two images, i.e., using computer-aided filter design techniques.
Conventional computer-aided filter design may be accomplished through using training-sets of document bitmaps, for example.
Illustratively, for designing a filter that enhances from a binary state to a gray-scale state, for a given pattern that occurs in the binary image about a target pixel, a training analysis system examines a target pixel at that corresponding location in the gray-scale image. The center of the window may be placed at the target pixel, for example. Based on the set of gray-scale pixels in the gray-scale image that are associated with corresponding target pixels in the binary image and gray-scale image, and associated with a similar neighborhood pixel pattern, a xe2x80x9cbest gray-scale pixel valuexe2x80x9d is determined for processing a target pixel that possess that pattern of neighborhood pixels. In other words, a template is created for the target pixels in the binary image possessing similar neighborhood pixel patterns. This analysis is performed for all binary patterns that are significant.
In this process of template selection, significance may be due to attributes such as the pixel pattern""s frequency of occurrence, the pattern""s effect on the generated image, or both. Accordingly, if a template, i.e., a pattern of pixels in the binary image, is considered significant with respect to template inclusion in the design process, that template will appear in the template-matching filter. Upon operating on an input image, if that pattern is observed, the observed target pixel value will be assigned or associated with a certain value, i.e., a corresponding gray-scale value. Both the observed neighborhood and the corresponding gray-scale value may be stored in the look-up table. Accordingly, the look-up table accepts input values and outputs a desired corresponding output value, i.e., maps input values to an ideal corresponding output value.
However, it should be apparent that this input/output process may be performed in various other ways without using a look-up table. One alternative approach that is equivalent to using a look-up table representation is a Boolean logic representation. In the Boolean logic representation, pixel values are used as variables in the logic architecture, such as a logical sum of products. The goal of template filter design using Boolean logic representation is to derive optimized Boolean operators, preferably statistically optimized Boolean operators.
As illustrated in FIG. 1 there is shown the basic process for template matching based on an observed image. Initially an observed image will occur (10) from which an ideal image is warranted (15). In order to generate an image as close as possible to the ideal image, a generated image (25) is created by utilizing a template matching operation (20). With the above understanding of the image processing setting we see that it is greatly desired to produce a generated image as similar as possible to the ideal image.
The conventional template matching operation is a binary matching process whereby a binary template or filter is to applied to a binary image.
For example, as illustrated in FIG. 2A a binary image (50) is initially sent to a data buffering circuit (55). After which, a binary pattern matching operation (60) is performed. Binary templates are typically defined as possessing ones, zeros, and xe2x80x9cdon""t cares.xe2x80x9d With reference to FIG. 2B there is shown a typical binary matching template structure. For example, the binary templates in this example are defined with ones and X""s for use in the binary matching step, where xe2x80x9cXxe2x80x9d denotes xe2x80x9cdon""t carexe2x80x9d. After combining the buffered image data and the templates in the binary pattern matching operation (60), an enhanced data buffering step (65) to create the enhanced image (70) is exercised.
Illustrated in FIGS. 4A, 4B, and 4C is the set of images associated with an image restoration application using a filter defined by templates representing particular Boolean functions applied to a received image. FIG. 3A shows a representation of a 3xc3x973 window and the positions of pixels (x1, . . . , x9). The filter defined by this window and the templates of FIG. 2B possesses the Boolean function representation shown in FIG. 3B as follows:
y=f(x1, x2, . . . , x9)=x5+x4x6+x1x9+x2x8+x3x7xe2x80x83xe2x80x83(1)
When employed as a translation-invariant filter, the singleton template x5 behaves as an identity operator: whatever pixels are valued one and zero in the input image are valued one and zero in the output image, respectively. OR""ed onto that identity image is the result of each 2-pixel logical product. The templates corresponding to those products possess structures that straddle the origin pixel. In this configuration a template can xe2x80x9cfitxe2x80x9d, or yield a 1, when positioned about a hole or break in a character stroke. Equation 1 is an example of an image processing operator that can be employed to repair breaks in character strokes within an image. FIG. 4 is an example of applying Equation 1 as a filter operating on an image, where FIG. 4A shows an ideal image, 4B shows an input image, and 4C shows the image resulting from applying Equation 1 as a filter to the image of FIG. 4B. The filter defined by Equation 1 produced a character (120) more likely to be recognized in character recognition operation. The restoration is not perfect. A more complicated (more and different products) filter could achieve better restoration. As shown in FIG. 4A and FIG. 4C there are still differences between the ideal image 100 and the generated image 120 resulting from the use of the filtering process defined by Equation 1.
As illustrated in FIG. 5A a system of the prior art is shown where an input image 150 is processed by a process 165 that includes binary-template-based filters 160 and combinatorial logic 170 [changed t to match the figure]; from which an output image 175 is generated and subsequently sent to a digital printer, high resolution printer or high resolution display 180.
The present invention is directed toward using loose-gray-scale template matching for recognition of features and/or characters in a document image. Character feature recognition is often referred to as Optical Character Recognition (OCR) in the art, and we may say that the present invention is directed towards OCR using a loose-gray-scale template matching process.
The present method is for feature recognition using loose-gray-scale template matching including at least an initial point for locating within the received image a plurality of pixel points in gray-scale surrounding an initial point. The method has the steps of first locating the initial point and the plurality of pixel points to define feature boundaries and then generating a looseness interval about the located initial point with template information being associated therewith. The next step involves determining which one of a plurality of templates for fitting fits within a threshold looseness interval, and then outputting a signal associated with that recognized feature.
Another aspect of the present invention is that the output signal associated with the matching template and recognized feature is used in subsequent processing to perform recognition of a larger or more global feature. For example, a collection of corners and strokes may be recognized and used as input to further recognition processing, for identification of characters. Another example is that currency marks may be recognized and provided as input to subsequent processing to identify monetary currency. The present invention therefore describes recognition of features at least two levels: recognition of the overall feature of interest (e.g., a character), recognition of smaller more primitive features such as a collection of corners to be used on a subsequent recognition algorithm for the overall feature.
Another aspect of the present invention is that the output signal associated with the matching template and recognized feature is used in subsequent processing to enhance the appearance of the feature, for example increasing the contrast or size of a small feature.
Another aspect of the present invention is that the output signal associated with the matching template and recognized feature is used in subsequent processing to perform a restoration from degradation process, an example of such restoration being the suppression or lightening degradation marks.